Previous | Index | Next |

Sorted Associated Containers

The additional requirements for sorted associative containers are given in the follwing table:

Sorted associative container requirements (in addition to base requirements).
expression return type assertion/note
pre/post-condition
complexity
X(c) . constructs an empty container;
uses c as a comparison object.
constant
X(i, j, c) . constructs an empty container and inserts elements from the range [i,j) into it;
uses c as a comparison object.
NlogN in general (N is the distance from i to j);
linear if [i,j) is sorted with c
a.key_comp() Predicate2 returns the comparison object out of which a was constructed. constant
a.insert(p, t) iterator inserts t if and only if there is no element with key equal to the key of t in containers with unique keys; always inserts t in containers with equal keys.
always returns the iterator pointing to the element with key equal to the key of t.
iterator p is a hint pointing to where the insert should start to search.
expected logarithmic in general, but expected amortized constant if t is inserted right before p.
a.lower_bound(k) Iterator returns an iterator pointing to the first element with key not less than k. logarithmic
a.upper_bound(k) Iterator returns an iterator pointing to the first element with key greater than k. logarithmic
a.equal_range(k) pair(Iterator,Iterator) equivalent to Pair(a.lower_bound(k), a.upper_bound(k)). expected logarithmic

The fundamental property of iterators of associative containers is that they iterate through the containers in the non-descending order of keys where non-descending is defined by the comparison that was used to construct them. For any two dereferenceable iterators i and j such that distance from i to j is positive,

    a.value_comp(j.get(), i.get()) == false
For associative containers with unique keys the stronger condition holds,
    a.value_comp(i.get(), j.get()) == true.


Previous | Index | Next |